package interview.algorithms.sort;

import common.Util;

/**
 * @author fance
 * @date 2018/7/15 19:45
 */
public class Again_Again {
    public void quickSort(int[] a, int n) {
        quickSort(a, 0, n - 1);
    }
    public void quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a,lo,hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }
    public int partition(int[] a, int lo, int hi) {
        int i = lo,j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }
            Util.swap(a,i,j);
        }
        Util.swap(a,lo,j);
        return j;
    }


    int leftChild(int i) {
        return 2 * i + 1;
    }
    void sink(int[] a,int i,int n) {
        int child;
        int tmp = a[i];
        for (; leftChild(i) < n ; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child + 1] > a[child]) {
                child++;
            }
            if (tmp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;

    }

    public void heapSort(int[] a,int n) {
        for (int i = n / 2; i >= 0; i--) {
            sink(a,i,n);
        }
        for (int i = n - 1; i > 0; i--) {
            Util.swap(a,0,i);
            sink(a,0,i);
        }
    }
}
